/************************************************************************/
/*    Author: Scott Bevin                                               */
/************************************************************************/

#pragma once

#include "../GraphCommon.h"

namespace XF
{
	template<class TGraphType>
	class GraphSearch
	{
	public:
		typedef typename TGraphType::EdgeType	EdgeType;
		typedef typename TGraphType::NodeType	NodeType;

	protected:
		TGraphType* mGraph;
		int mSourceID, mTargetID;

		virtual void OnInitSearch() = 0;
		virtual bool OnDoStep() = 0;

		bool mFoundPath;

	public:
		GraphSearch(TGraphType *graph) : 
				mGraph(graph), 
				mSourceID(XF_INVALID_NODE_INDEX), 
				mTargetID(XF_INVALID_NODE_INDEX) {}

		virtual ~GraphSearch() {}

		bool FoundPath()
		{
			std::list<int> path = GetPathToTarget();

			return (std::find(path.begin(), path.end(), mTargetID) != path.end() &&
					std::find(path.begin(), path.end(), mSourceID) != path.end());
		}

		void InitSearch(int sourceID, int targetID)
		{
			mSourceID = sourceID;
			mTargetID = targetID;

			OnInitSearch();
		}

		bool DoStep(){return OnDoStep();}

		void PerformSearch(int sourceID, int targetID)
		{
			mFoundPath = false;

			InitSearch(sourceID, targetID);

			while(!FinishedSearching())
			{
				if(DoStep())
				{
					mFoundPath = true;
					break;
				}
			}
		}

		virtual bool FinishedSearching() = 0;

		virtual std::vector<int> GetAllPaths() = 0;
		virtual std::list<int> GetPathToTarget() = 0;
		virtual double GetCostToTarget() = 0;
	};
}
